package 双指针.二分查找;

/**
 * 解题思路：
 * 首先可以简单的给题目分为两种情况
 * 1、target比char[]中的都大，这时候直接返回char[0]
 * 2、char[]中有值大于target
 * 如果有值大于target，那么我们就用二分查找法，缩小区间来找到该值。
 * 首先left=0；right=char[].length-1;  mid为(left+right)/2;
 * 然后再进行遍历，如果有mid=target，那么要求的就是mid+1（char[]中大于target的最小值）；
 */
public class
寻找比目标字母大的最小字母_744 {
    public static void main(String[] args) {
        char[] l = {'c', 'f', 'j'};
        char target = 'c';
        System.out.println(new 寻找比目标字母大的最小字母_744().nextGreatestLetter(l, target));

    }

    public static char nextGreatestLetter(char[] letters, char target) {
        int left = 0;
        int right = letters.length - 1;

        if (target >= letters[letters.length - 1]) {//循环比较的处理
            return letters[0];
        } else {
            while (left < right) {//之所以不用<=是为了防止出现left=0，right=0，的情况，如果出现了那么  mid=(0+0)/2明显有错误。
                int mid = (left + right) / 2;
                if (letters[mid] <= target) {
                    left = mid + 1;
                }

                /*
                本来right应该等于mid-1，但是也是为了防止出现left=right=0的情况，如果出现会导致少循环一次，进而导致错误
                例如：char["c","f","j"] target="c"
                如果right=mid-1，输出"c"（错误），
                如果right=mid，输出”f“（正确）
                 */
                if (letters[mid] > target) {
                    right = mid;
                }
            }
            return letters[left];
        }

    }
}
